#include <iostream>
#include <vector>
#include <stdlib.h>
#include <assert.h>
#include <list>
#include <deque>
#include <algorithm>
#include <iterator>

using namespace std;

struct Entry {
    int val;
    int src;
    Entry ( int v, int s)
	    : val( v ),
	      src( s ) {
    }
};

bool operator<( Entry const & a, Entry const & b ) { return a.val < b.val; }
ostream &operator<<( ostream &o, Entry const &e ) {
    o << e.val;
    return o;
}

int left_child( int i ) { return i*2+1; }
int right_child( int i ) { return i*2+2; };
int parent( int i ) { return (i-1)/2; }
void swap( Entry *a, Entry *b ) { Entry t = *a; *a = *b; *b = t; }
void sift_down( Entry *begin, int cursor, Entry *end ) {
    const int last = end - begin;
    while( cursor < last ) {
	int next = cursor;
	const int right = right_child( cursor );
	const int left = left_child( cursor );
	if ( right < last && begin[right] < begin[next] ) {
	    next = right;
	}
	if ( left < last && begin[left] < begin[next] ) {
	    next = left;
	}
	if ( next == cursor ) break;
	swap( begin+next, begin+cursor );
	cursor = next;
    }
}

void heapify( Entry *begin, Entry *end ) {
    int cursor = end - begin;
    while ( cursor >= 0 ) {
	sift_down( begin, cursor, end );
	cursor--;
    }
}

template< class ForwardIterator >
void merge( list<int> &result, 
            vector< pair< ForwardIterator, ForwardIterator > > input ) {

    typedef pair< ForwardIterator, ForwardIterator > Pair;
    typedef vector< Pair > Input;

    vector< Entry > heap;
    for ( unsigned i = 0; i < input.size(); i++ ) {
	if ( input[i].first == input[i].second ) continue;
	heap.push_back( Entry( *input[i].first, i ) );
	input[i].first++;
    }

    heapify( &heap.front(), &heap.back()+1 );

    while ( heap.size() ) {
	result.push_back( heap.front().val );
	Pair &q = input[heap.front().src];
	if ( q.first == q.second ) {
	    heap.front() = heap.back();
	    heap.pop_back();
	} else {
	    heap.front() = Entry( *q.first, heap.front().src );
	    q.first++;
	}
	sift_down( &heap.front(), 0, &heap.back()+1 );
    }
}

void merge_adapter( list< int > &out, vector< deque < int > > const &in ) {
    typedef vector< deque< int > >::const_iterator DIterator;
    typedef deque< int >::const_iterator IIterator;
    typedef pair< IIterator, IIterator > Pair;
    vector< Pair > newarg;
    for ( DIterator it = in.begin(); in.end() != it; it++ ) {
	newarg.push_back( Pair( it->begin(), it->end() ) );
    }
    merge( out, newarg );
}

void merge_adapter( list< int > &out, vector< vector < int > > const &in ) {
    typedef vector< vector< int > >::const_iterator DIterator;
    typedef vector< int >::const_iterator IIterator;
    typedef pair< IIterator, IIterator > Pair;
    vector< Pair > newarg;
    for ( DIterator it = in.begin(); in.end() != it; it++ ) {
	newarg.push_back( Pair( it->begin(), it->end() ) );
    }
    merge( out, newarg );
}

template<class RandomAccess>
int printIt( vector< RandomAccess > const &in ) {
    for ( unsigned i = 0; i < in.size(); i++ ) {
	for ( unsigned j = 0; j < in[i].size(); j++ ) {
	    cout << in[i][j] << " ";
	}
	cout << endl;
    }
    cout << endl;
}

int main ( int argc, char * argv[] ) {
    unsigned m(20), k(2), s(1);
    // cin >> m >> k >> s;
    srand( s );
    
    vector< vector< int > > in;
    for ( unsigned i = 0; i < m; i++ ) {
        vector< int > res;
        for ( unsigned j = 0; j < k; j++ ) {
            res.push_back( rand() % 10 );
        }
        in.push_back( res );
    }

    printIt( in );

    for ( unsigned i = 0; i < in.size(); i++ ) {
        sort( in[i].begin(), in[i].end() );
    }

    printIt( in );

    list< int > out;
    merge_adapter( out, in );

    cout << "out : "; 
    copy( out.begin(), out.end(), ostream_iterator<int>( cout, " " ) );
    cout << endl;
}
